908D - New Year and Arbitrary Arrangement - CodeForces Solution

#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define sws ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define teto(a, b) ((a+b-1)/(b))
using namespace std;

// Extra
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//

const int MAX = 300010;
const ll MOD = (int)1e9 +7;
const int INF = 1e9;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ld EPS = 1e-8;

ll fexp(ll b, ll e) {
    if(e == 0) return 1;
    ll res = fexp(b, e/2);
    res = (res * res) % MOD;
    if(e%2) res = (res * b) % MOD;
    return res; 
}

ll inv(ll a) {
    return fexp(a, MOD-2);
}

ll k, pa, pb;
ll tab[2002][2002];
ll ipapb;

ll dp(int qa, int s) {
    if(qa >= s) {
        ll p = (pa * ipapb) % MOD;
        return (qa + p*inv(MOD + 1-p)) % MOD;
    }
    if(s <= 0) {
        return 0;
    }

    if(tab[qa][s] != -1) return tab[qa][s];

    ll pegaa = (dp(qa+1, s) * pa) % MOD;
    pegaa = (pegaa * ipapb) % MOD;

    ll pegab = ((qa + dp(qa, s-qa)) * pb) % MOD;
    pegab = (pegab * ipapb) % MOD;

    ll res = (pegaa + pegab) % MOD;

    return tab[qa][s] = res;
}

int main() {
    sws;
    memset(tab, -1, sizeof(tab));
    cin >> k >> pa >> pb;

    ipapb = inv(pa + pb);

    cout << dp(1, k) << endl;

    return 0;
}